/** An engine to calculate binomial tree and price based on it */

package pricingEngine;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;

import payout.OptionA;
import payout.Payout;
import payout.StandardCall;
import payout.StandardPut;

import variance.BlackScholes;
import yieldCurve.*;

/** A class to build a binomial tree and estimate option prices from it.
 * 
 * @author spoulton, tliu2
 *
 */
public class Binomial extends Engine {
	// the last two columns of the binomial tree, interleaved
	ArrayList<Double> S_lattice;
	
	// an array of premium values.
	ArrayList <Double> payoutArray;

	// Option exercise type selection
	OptionType type;

	// the variables affecting price changes
	double a, u, d, p;
	
	// continuous risk-free rate
	double r;
	
	// the number of intervals (i.e. the number of layers plus one)
	int N;
	
	// the interval ratio
	double deltat;
	
	/** Class constructor. Sets up main variables required for tree building.
	 * 
	 * @param sigma Sigma, i.e. variance
	 * @param expiryDate Expiry date of the option
	 * @param N The number of steps (i.e. one less than the number of nodes)
	 * @param S0 Initial market value
	 * @param strike Strike price
	 */
	public Binomial(YieldCurve yieldCurve, double sigma, double S0, double strike, 
			Date startDate, Date expiryDate, Payout payout, int N, OptionType optionType) {
		super(yieldCurve, sigma, S0, strike, startDate, expiryDate, payout);
		startDate = Date.businessDay(startDate);
		System.out.println("today:" + startDate);
		System.out.println("expiry:" + expiryDate);
		this.N = N;
		this.type = optionType;
		deltat = (Date.getDeltaT(startDate, expiryDate))/N;
		System.out.println("delta:" + Date.getDeltaT(startDate, expiryDate));
		u = Math.exp(sigma*Math.sqrt(deltat));
		d = 1/u;
		r = yieldCurve.getContinuousCompound(deltat*N);
		a = Math.exp(r*deltat);
		p = (a - d)/(u - d);
		System.out.println("deltat:"+deltat+"  u:"+u+"  d:"+d);
	}
	
	/**
	 * inheriting the super class, add 2 extra field, M, N
	 * @param S0
	 * @param strike
	 * @param startDate
	 * @param expiryDate
	 * @param payoutArray
	 * @param M the number of trials
	 * @param N the number of intervals (i.e. the number of layers plus one)
	 */
	public void setOptionInfo(double S0, double strike, 
			Date startDate, Date expiryDate, Payout payout, int N) {
		super.setOptionInfo(S0, strike, startDate, expiryDate, payout);
		this.N = N;
	}

	/** The main Binomial method. Constructs a tree, traces it back, and determines a price.
	 * 
	 * @param yc The yield curve, as calculated based on the inputs of the file
	 * @param opt Option exercise type - American or European.
	 * @return
	 */
	public double getOptionPrice(){
		S_lattice = new ArrayList <Double>();
		double a_reciprocal = 1/a; // for the inner loop, since multiply by reciprocal is faster than divide.
		double dummy1 = 0;
		double dummy2 = 0;
		
		if(Runtime.getRuntime().maxMemory() < N*18) { // 2N * 8byte doubles + a bit extra for the rest of the function
			throw new Error("The heap size is too small for this amount of N");
		}
			 
		// S_lattice represents the binomial tree's possible values of S.
		// It does this by storing the last two columns of the tree, interleaved, as a list.
		// You can get the S value of any node by accessing the ((pos+depth)*2)th element,
		// where "pos" is the distance from the top (with the tree viewed in the traditional
		// left-to-right manner) and "depth" is the distance from the right, both zero-indexed.
		for (int i=N;i>=-N;i--) {
			S_lattice.add(S0*Math.pow(u, i));
		}
		
		// Calculate the payoutArray of the final (right-hand) layer.
		// payoutArray value is what is indicated as "c" in the lecture notes.
		payoutArray = new ArrayList<Double>();

		for ( int i = 0 ; i < S_lattice.size() ; i+=2 ){
			payoutArray.add(payout.getPayout(S_lattice.get(i),strike, dummy1, dummy2));
		}
		
		// Constructing back from right to left, calculating the payoutArray from each node.
		int size = payoutArray.size();
		for( int layer = N ; layer >0 ; layer--){
			if(type ==OptionType.O_AMERICAN) {
				for ( int i = 0 ; i < size - 1 ; i++){
					// NOTICE: The following line is quite long for speed reasons, so here is an easier to read equivalent in 6 lines:
					//	 double payout_average = p*payoutArray.get(i) + (1-p)*payoutArray.get(i+1);
					//	 double a = Math.exp(r*deltat);           // a=e^r*deltat
					//	 double base_c = payout_average / a;      // Recall that X/e^Y == X*e^-Y
					//	 double payout_if_exercised = payoutFunction.payoutArray(S_lattice.get((i+N-layer)*2), strike );
					//	 double american_c = Math.max(base_c, payout_if_exercised);  // Highest of the two values
					//	 payoutArray.set(i, american_c);
					payoutArray.set(i, Math.max((p*payoutArray.get(i) + (1-p)*payoutArray.get(i+1)) * a_reciprocal, 
							payout.getPayout(S_lattice.get(2*i+1+N-layer), strike, dummy1, dummy2)));
				}
			} else { // European option
				for ( int i = 0 ; i < size - 1 ; i++){
					// See comments on American option above for how to read this line.
					payoutArray.set(i, (p*payoutArray.get(i) + (1-p)*payoutArray.get(i+1)) * a_reciprocal);
				}
			}
			payoutArray.remove(payoutArray.size()-1);
			size--;
		}
		// only one payoutArray remains at the end of the tree - this is the leftmost point.
		return payoutArray.get(0);
	}
	
	public double getOptionPrice(OptionType type) {
		this.type = type;
		return getOptionPrice();
	}
	

	/** Binomial tree test program entry point
	 *  This method is not used when the system is run from userInterface.
 	 */
	static public void main(String Args[]){
		// Test settings here
		double S0 = 89.31;
		double strike = 95.0;
		double benchmark = 25.0;
		int Ninit;
		int Nmax;
		int step;
		PrintWriter priceWriterAm;
		PrintWriter priceWriterEu;

		// For making graphs of results with varying N.
		if(Debug.PROFILING == true) {
			Ninit=105000;
			Nmax=120000;
			step=5000;
		} else {
			Ninit=50000;
			Nmax=50000;
			step=1000;
		}
		
		Date today = new Date(2009,5,1);
		Date expiry = new Date(2011,1,22);
		Payout payout = new StandardCall();

		// build yield curve and calculate volatility
		YieldCurve yieldCurve = new YieldCurve("curveDataInput.csv", "curveSpec.csv", 2, today);
		BlackScholes bc = new BlackScholes(yieldCurve, S0, today, expiry, strike, benchmark);
		double sigma = bc.getSigma();
		System.out.println("volatility=" + sigma);

		try {
			if(Debug.PROFILING == true) {
				priceWriterAm = new PrintWriter(new BufferedWriter(new FileWriter("BnAm" + payout.getClass().getName() 
							+ "-" + today.toString() + "-N" + Nmax + ".txt")));
				priceWriterEu = new PrintWriter(new BufferedWriter(new FileWriter("BnEu" + payout.getClass().getName() 
						+ "-" + today.toString() + "-N" + Nmax + ".txt")));
			}
			// run tests!
			for(int N=Ninit;N<=Nmax;N+=step) {

				long start_time = System.currentTimeMillis();		
				Binomial bio = new Binomial(yieldCurve, sigma, S0, strike, 
						today, expiry, payout, N, OptionType.O_AMERICAN);
				double am = bio.getOptionPrice(OptionType.O_AMERICAN);
	
				long halfway_time = System.currentTimeMillis();
				double eu = bio.getOptionPrice(OptionType.O_EUROPEAN);
		
				long stop_time = System.currentTimeMillis();
			
				DecimalFormat df2 = new DecimalFormat( "#,###,###,##0.00" );
				double am_rounded = new Double(df2.format(am)).doubleValue();
				double eu_rounded = new Double(df2.format(eu)).doubleValue();
				System.out.println("American option price: $" + am_rounded + "  (or "+ am + "), took " 
					+ (halfway_time-start_time) + "ms to calculate with N=" + N);
				System.out.println("European option price: $" + eu_rounded + "  (or "+ eu + "), took "
					+ (stop_time-halfway_time) + "ms to calculate with N=" + N);
				System.out.println("Total time elapsed: " + (stop_time-start_time) + "ms");
				if(Debug.PROFILING == true) {
					priceWriterAm.println(N + "," + am + "," + (stop_time-start_time));
					priceWriterEu.println(N + "," + eu + "," + (stop_time-start_time));
				}
			}
			if(Debug.PROFILING == true) {
				priceWriterAm.close();
				priceWriterEu.close();
			}
		} catch (IOException e) {
			e.printStackTrace();
			System.err.println("End of stream");
		}
	}

}
